package com.test;

import java.util.Arrays;

/*
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，
 * 需要参与挖掘的工人人数也不同。
 * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；
 * 有的金矿储量是200kg黄金，需要3个工人 来挖掘……
 * 如果参与挖矿的工人的总数是10。
 * 每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
 * 要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 * */
public class Test2 {

    /*
    * 动态规划问题建模阶段
      假设
      工人：10 名
      金矿：400金/5人、500金/5人、200金/3人、300金/4人、350金/3人
      设金矿数量为N, 工人数量为W, 金矿黄金量为G[], 金矿用工量为P[]
      工人数     | 0  1  2   3   4    5    6    7    8    9    10
      ——————————-+———————————————————————————————————————————————
      第一座金矿  | 0  0  0   0    0   400  400  400  400  400  400
      第二座金矿  | 0  0  0   0    0   500  500  500  500  500  900
      第三座金矿  | 0  0  0  200  200  500  500  500  700  700  900
      第四座金矿  | 0  0  0  200  300  500  500  500  700  800  900
      第五座金矿  | 0  0  0  350  350  500  550  650  850  850  900

      规律：
          3金矿8工人  = max( 2金矿8工人, 2金矿5工人+第三座金矿)  = max(500, 500+200)
          5金矿10工人 = max( 4金矿10工人, 4金矿7工人+第五座金矿) = max(900, 500+350)
          ……
    由此可见，只需要存储前一行的结果，就可以推导出新的一行。
    *
    * 最优子结构：
      由于第五座金矿可挖可不挖，所以 10 人 5 座金矿的最优子结构有两种（选最大值）:
      10 人 4 座金矿的挖金总量 和 前四座金矿的挖金总量 + 第五座金矿的挖金总量
      = Max( F(4,10), F( 4,10-P[4] ) + G[4] )

    * 边界：
      只有一座金矿时，如果工人够，那就是金矿的黄金量；如果工人不够，挖金总量就是 0
      当 N = 1, W >= P [0] 时，F (N,W) = G [0];
      当 N = 1, W <P [0] 时，F (N,W) = 0

    * dp：
      取最后一座金矿挖与不挖的最大值
      F(N, W) = max( F(N - 1, W), F(N - 1, W - P[N - 1]) + G[N - 1] ) ,( N > 1, W >= P[N - 1] )
    *
    * */
    public static void findGold() {
        int w = 10;
        int[] p = new int[]{5, 5, 3, 4, 3};
        int[] g = new int[]{400, 500, 200, 300, 350};
        int[] results = new int[w + 1];
        for (int i = 1; i <= g.length; i++) {
            for (int j = w; j >= 1; j--) {
                if (j >= p[i - 1]) {
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        // 返回最后1个格子的值 900
        System.out.println(results[w]);
    }


    public static void main(String[] args) {
        findGold();
    }


}
